package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;

/**
 * @author tzp
 * @since 2020/9/22
 */
public class LC518_1 implements DynamicProblem {

    int[][] dp;
    int[] coins;

    public int change(int amount, int[] coins) {
        if (amount == 0) return 1;
        Arrays.sort(coins);
        this.coins = coins;
        this.dp = new int[coins.length][amount + 1];
        for (int[] row : dp) Arrays.fill(row, -1);
        return re(amount, 0);
    }

    public int re(int amount, int start) {
        if (amount < 0) return 0;
        if (start >= coins.length) return 0;
        if (amount == 0) {
            dp[start][amount] = 1;
            return 1;
        }
        if (dp[start][amount] != -1)
            return dp[start][amount];

        if (coins[start] == amount) {
            dp[start][amount] = 1;
            return 1;
        }
        if (coins[start] > amount) {
            dp[start][amount] = 0;
            return 0;
        }
        if (start + 1 == coins.length) {
            return amount % coins[start] == 0 ? 1 : 0;
        } else {
            int total = 0;
            for (int remain = amount; remain >= 0; remain -= coins[start]) {
                total += re(remain, start + 1);
            }
            dp[start][amount] = total;
            return total;
        }
    }

    public static void main(String[] args) {
//        System.out.println(new LC518_1().change(5, new int[]{1, 2, 5}));
//        System.out.println(new LC518_1().change(3, new int[]{2}));
        System.out.println(new LC518_1().change(10, new int[]{5}));
    }
}
